# (c) Copyright 2008 Paul Hankin. All Rights Reserved. 

"""Provide functions for listing all legal moves from a given position."""

from main import Move, Board

def enumerate_move1(board, d, at_most=25):
    """Generate all legal moves for a single dieroll. at_most limits
    the highest move considered. The function yields (from, to), board
    where from and to are the points moved from and to, and board is
    the final board position."""
    bearing_off = all(board[i] <= 0 for i in xrange(7, 26))
    for p in xrange(at_most, 0, -1):
        # Men on bar: don't allow any move that's not from the bar
        if p < 25 and board[25] > 0: break
        # No men on this point: don't allow move
        if board[p] <= 0: continue
        # Don't allow a move onto a point where opponent has men
        if p - d > 0 and board[p - d] < -1: continue
        # Moving off exactly; only allowed if no men above 6 point.
        if p - d == 0 and not bearing_off: continue
        # Moving off inexactly: only allowed if bearing off, and no men
        # above our point.
        if p - d < 0 and not bearing_off: continue
        if p - d < 0 and any(board[i] > 0 for i in xrange(p + 1, 7)):
            continue
        # Make a board for the new position
        b_ret = list(board)
        # Remove the moved man
        b_ret[p] -= 1
        # Add the moved man to its new square (unless it's bearing off)
        if p - d > 0:
            # Deal with hit first
            if b_ret[p - d] == -1:
                # We've hit: move the hit man to the bar
                b_ret[p - d], b_ret[0] = 0, b_ret[0] - 1
            b_ret[p - d] += 1
        yield (p, max(0, p - d)), b_ret

def enumerate_moves_doublet0(board, r, moves, count, at_most, found_boards):
    """Enumerate move played with 'count' rolls of 'r', played from the
    'at_most' point or lower. The move is accumulated (backwards) in 'moves'
    and found_boards is a set of moves found so far, to prevent duplicates
    and duplicate searching. The resulting board positions are yielded, and
    at the time of yielding 'moves' contains the (reversed) current move."""
    for ft0, b0 in enumerate_move1(board, r, at_most):
        b0 = tuple(b0)
        if b0 not in found_boards:
            found_boards.add(b0)
            moves[count - 1] = ft0
            if count == 1:
                yield b0
            else:
                for b1 in enumerate_moves_doublet0(b0, r, moves, count - 1,
                                                 ft0[0], found_boards):
                    yield b1

def enumerate_moves(board, dice0, dice1):
    "Generate all legal moves for a given roll."
    dice1, dice0 = sorted([dice0, dice1])
    if dice0 == dice1:
        # A doublet. Deal with it separately.
        # This uses a naive approach: try using all 4 dice, then
        # 3, then 2, then 1.
        for count in xrange(4, 0, -1):
            found = False
            moves = [None] * count
            for b0 in enumerate_moves_doublet0(board, dice0, moves, count,
                                             25, set()):
                yield Move(board, *reversed(moves)), Board(b0)
                found = True
            if found:
                break
        return

    used_both = False
    found_boards = set()
    # Try playing dice in high-low order first, then low-high.
    # We keep a set of target board positions so we don't ever
    # return duplicate moves.
    for d0, d1 in ((dice0, dice1), (dice1, dice0)):
        for ft0, b0 in enumerate_move1(board, d0):
            for ft1, b1 in enumerate_move1(b0, d1, ft0[0]):
                b1 = tuple(b1)
                if b1 not in found_boards:
                    found_boards.add(b1)
                    used_both = True
                    yield Move(board, ft0, ft1), Board(b1)
    if not used_both:
        # We've found no moves: try using a single dice. Try larger
        # die first and abort if we find moves for that, to satisfy the
        # rule that if either dice (but not both) can be used, it must be
        # the larger.
        for d0 in (dice0, dice1):
            found_one = False
            for ft0, b0 in enumerate_move1(board, d0):
                b0 = tuple(b0)
                if b0 not in found_boards:
                    found_boards.add(b0)
                    found_one = True
                    yield Move(board, ft0), Board(b0)
            if found_one: break

